Corelab Seminar
2017-2018
Evangelos Kranakis
Linear Search with Faulty Robots
Abstract.
There are n mobile communicating robots, of which at most f are faulty, and the remaining n-f are reliable. A treasure is placed on the geometric domain at a location unknown to the robots. Reliable robots can find the treasure only when they reach its location, but faulty robots either cannot detect the treasure (crash faulty) or may maliciously report a wrong location (Byzantine faulty). Our goal is to design search (resp. evacuation) algorithms minimizing the competitive ratio, represented by the worst case ratio between the time of arrival of the first (resp., last) reliable robot at the treasure, and the distance from the ``sources'' to the treasure. We present several recent results that illuminate tradeoffs on the impact of fault tolerance and communication on search time.